#include "MinHeap.h"

// 创建小根堆
MinHeap *CreateMinHeap(int capacity)
{
    MinHeap *minHeap = (MinHeap *)malloc(sizeof(MinHeap));
    minHeap->capacity = capacity;
    minHeap->size = 0;
    minHeap->array = (CacheNode *)malloc(minHeap->capacity * sizeof(CacheNode));
    return minHeap;
}

// 交换两个节点
void Swap(CacheNode *a, CacheNode *b)
{
    CacheNode temp = *a;
    *a = *b;
    *b = temp;
}

// 获取节点的左子节点索引
int Left(int i) { return 2 * i + 1; }

// 获取节点的右子节点索引
int Right(int i) { return 2 * i + 2; }

// 获取节点的父节点索引
int Parent(int i) { return (i - 1) / 2; }

// 向上调整堆
void HeapifyUp(MinHeap *minHeap, int index)
{
    int p = Parent(index);
    if (index && minHeap->array[index].frequency < minHeap->array[p].frequency)
    {
        Swap(&minHeap->array[index], &minHeap->array[p]);
        HeapifyUp(minHeap, p);
    }
}

// 向下调整堆
void HeapifyDown(MinHeap *minHeap, int index)
{
    int smallest = index;
    int l = Left(index);
    int r = Right(index);

    if (l < minHeap->size && minHeap->array[l].frequency < minHeap->array[smallest].frequency)
    {
        smallest = l;
    }
    if (r < minHeap->size && minHeap->array[r].frequency < minHeap->array[smallest].frequency)
    {
        smallest = r;
    }
    if (smallest != index)
    {
        Swap(&minHeap->array[index], &minHeap->array[smallest]);
        HeapifyDown(minHeap, smallest);
    }
}

// 插入节点到小根堆
void HeapInsert(MinHeap *minHeap, char *key)
{
    if (minHeap->size == minHeap->capacity)
    {
        printf("Heap is full. Cannot insert more elements.\n");
        return;
    }

    CacheNode newNode = {key, 1};
    minHeap->array[minHeap->size] = newNode;
    HeapifyUp(minHeap, minHeap->size);
    minHeap->size++;
}

// 删除最小元素（使用频率最低的元素）
CacheNode ExtractMin(MinHeap *minHeap)
{
    if (minHeap->size <= 0)
    {
        printf("Heap is empty.\n");
        return (CacheNode){NULL, -1};
    }

    CacheNode root = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    minHeap->size--;
    HeapifyDown(minHeap, 0);

    return root;
}

// 增加节点的使用频率
void IncreaseFrequency(MinHeap *minHeap, char *key)
{
    for (int i = 0; i < minHeap->size; i++)
    {
        if (strcmp(minHeap->array[i].key, key) == 0)
        {
            minHeap->array[i].frequency++;
            HeapifyDown(minHeap, i);
            return;
        }
    }
    printf("%s节点不存在!!\n", key);
}

// 打印小根堆
void PrintHeap(MinHeap *minHeap)
{
    for (int i = 0; i < minHeap->size; i++)
    {
        printf("Key: %s, Frequency: %d\n", minHeap->array[i].key, minHeap->array[i].frequency);
    }
}

//销毁小根堆
void DestroyHeap(MinHeap *minHeap)
{
    if(minHeap == NULL)
    {
        return;
    }
    free(minHeap->array);
    free(minHeap);
    minHeap = NULL;
}
